In some systems, a plurality of devices such as a processor, decoder, etc. (hereinafter referred to as “masters”) are connected by a bus to a memory so that the masters share the memory.
In such a system, an arbitration device is provided to address the issue of memory contention among memory use requests from the masters. The arbitration device selects one of the contending memory use requests and outputs it as the memory use request having the highest priority.
Based, for example, on previously determined information that indicates a priority ranking of memory use requests, the arbitration device selects and outputs the contending memory use request having the highest priority.
In systems where a plurality of masters use the memory, only the master that issued the memory use request having the highest priority output by the arbitration device is permitted to use the memory via the bus.
Patent Literature 1, for example, discloses technology for a plurality of masters to share a memory.
In systems where a plurality of masters share the memory, arbitration devices may be structured hierarchically out of consideration for timing or the length of physical wiring in cases such as when the number of masters is large, or when the masters are physically separate from one another.
Hierarchically structured arbitration devices are structured with an arbitration device at each level in the hierarchy to arbitrate memory use requests at that level. These arbitration devices are connected to each other in a daisy-chain or tournament style.
The arbitration device at a lower level in the hierarchy receives memory use requests from masters belonging to that level, selects the memory use request having the highest priority, and outputs the selected memory use request to the arbitration device that is one level higher.
The arbitration device that is one level higher in the hierarchy receives memory use requests from masters belonging to that level and from the arbitration device at the lower level, selects the memory use request having the highest priority, and outputs the selected memory use request to the arbitration device that is yet one level higher.
In this way, starting at the lowest level of the hierarchy, each arbitration device in the hierarchy selects the memory use request having the highest priority among the level of the arbitration device and lower levels and outputs the memory use request to the arbitration device that is the next level up in the hierarchy. Ultimately, the memory use request having the highest priority as output by the arbitration device at the highest level in the hierarchy becomes the memory use request having the highest priority in the system.
However, since the arbitration devices in the hierarchy arbitrate in order from the lowest level, it is difficult to physically dispose the circuit so as to shorten processing time between the start of arbitration and the output of the memory use request having the highest priority.
Typically, when a memory controller or the like receives the memory use request having the highest priority output from the arbitration device, the memory controller allows the master that issued the memory use request to use the memory.
The interval from the arbitration device outputting the memory use request having the highest priority and the master receiving a response signal from the memory controller for the memory use request until the next memory use request having the highest priority occurs is hereinafter referred to as “latency”. When the period of memory used by the master receiving the response signal is shorter than the latency, the memory is not used during the time difference between the latency and the period of memory use, a phenomenon hereinafter referred to as the “bubble phenomenon”.
In a memory use system employing hierarchical arbitration devices, it is difficult to reduce the latency of the hierarchical arbitration devices, and therefore the problem of the bubble phenomenon may occur.
Patent Literature 2 discloses an example of technology to reduce occurrence of the bubble phenomenon in a memory use system employing hierarchical arbitration devices.
This technology for hierarchical arbitration devices provides, between a lower level and an upper level, a cache memory for temporarily storing data in the main memory used in response to a memory use request. If the memory use request having the highest priority in the lower level hits the cache memory, the cache memory is used instead of the main memory.
With this technology, if a memory use request at a lower level hits the cache memory, the cache memory is used without waiting for the results of arbitration at higher levels. Accordingly, when the memory use request hits the cache memory, the memory use system employing hierarchical arbitration devices performs as though the above latency had become shorter.